a. Field of the Invention
The instant invention relates to surface modeling. In particular, the instant invention relates to a system and method for reconstruction of a surface from an unstructured cloud of data points.
b. Background Art
It is well known to generate heart chamber geometry in preparation for cardiac diagnostic or therapeutic procedures. Often, a mapping catheter is introduced into the heart chamber of interest and moved around within the heart chamber, either randomly, pseudo-randomly, or according to one or more preset patterns. The three-dimensional coordinates of the mapping catheter are measured using a localization system (sometimes also referred to as a “mapping system,” “navigation system,” or “positional feedback system”). The three-dimensional coordinates become a geometry point (or “location data point”). Multiple measurements may be taken as the catheter is moved within the heart chamber, resulting in a cloud of geometry points that defines the geometry of the heart chamber. Various surface construction algorithms may then be applied to wrap a surface around the cloud of geometry points to obtain a surface representation of the heart chamber geometry.
One such surface construction algorithm generates a convex hull about the cloud of geometry points. The convex hull may be generated using standard algorithms such as the Qhull algorithm. The Qhull algorithm is described in Barber, C. B., Dobkin, D. P., and Huhdanpaa, H. T., “The Quickhull algorithm for convex hulls,” ACM Trans. on Mathematical Software, 22(4):469-483, December 1996. Other algorithms used to compute a convex hull shape are known and may also be suitable for use in implementing the invention.
Another surface construction algorithm is Alpha Shapes. The alpha shape is a generalization of the convex hull and a subgraph of the Delaunay triangulation. For a sufficiently large alpha, the alpha shape is identical to the convex hull, while for a sufficiently small alpha, the alpha shape is empty.
Another exemplary method for creating a shell corresponding to the shape of the heart chamber fits a radial array of bins around groups of geometry points. The bins are typically constructed by determining a mean center point of the cloud of geometry points and extending borders radially outward from the mean center point to the furthest geometry point within the slice encompassed by the bin. The radial end faces of the bins thus approximate the surface of the heart chamber wall. Common graphic shading algorithms can then be employed to “smooth” the surface of the shell thus created out of the radial end faces of the bins.
Existing surface reconstruction algorithms have certain shortcomings, however. For example, by definition, convex hull algorithms cannot be used to estimate non-convex boundaries, while algorithms using alpha shapes are computationally intensive.